package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/design-circular-deque/">设计循环双端队列(Design Circular Deque)</a>
 * <p>
 * 设计实现双端队列。实现 MyCircularDeque 类:
 * <ul>
 *     <li>MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。</li>
 *     <li>boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。</li>
 *     <li>boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。</li>
 *     <li>boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。</li>
 *     <li>boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。</li>
 *     <li>int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。</li>
 *     <li>int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。</li>
 *     <li>boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。</li>
 *     <li>boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。</li>
 * </ul>
 * </p>
 * <p>
 * <pre>
 * 示例 1：
 *      输入
 *          ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
 *          [[3], [1], [2], [3], [4], [], [], [], [4], []]
 *      输出
 *          [null, true, true, true, false, 2, true, true, true, 4]
 *      解释
 *          MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
 *          circularDeque.insertLast(1);			        // 返回 true
 *          circularDeque.insertLast(2);			        // 返回 true
 *          circularDeque.insertFront(3);			        // 返回 true
 *          circularDeque.insertFront(4);			        // 已经满了，返回 false
 *          circularDeque.getRear();  				// 返回 2
 *          circularDeque.isFull();				        // 返回 true
 *          circularDeque.deleteLast();			        // 返回 true
 *          circularDeque.insertFront(4);			        // 返回 true
 *          circularDeque.getFront();				// 返回 4
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= k <= 1000</li>
 *     <li>0 <= value <= 1000</li>
 *     <li>insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0622MyCircularQueue_M 设计循环队列(Design Circular Queue)
 * @see LC0641MyCircularDeque_M 设计循环双端队列(Design Circular Deque)
 * @since 2023/5/10 13:40
 */
public class LC0641MyCircularDeque_M {

    static class MyCircularDeque {
        /**
         * 虚拟头节点
         */
        Node dummyHead;
        /**
         * 虚拟尾节点
         */
        Node dummyTail;
        /**
         * 元素个数
         */
        int size;
        /**
         * 链表容量
         */
        int capacity;

        public MyCircularDeque(int k) {
            this.capacity = k;
            dummyHead = new Node(-1);
            dummyTail = new Node(-1);
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }
            Node newNode = new Node(value);
            newNode.next = dummyHead.next;
            newNode.prev = dummyHead;
            dummyHead.next.prev = newNode;
            dummyHead.next = newNode;
            ++size;
            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }
            Node newNode = new Node(value);
            newNode.next = dummyTail;
            newNode.prev = dummyTail.prev;
            dummyTail.prev.next = newNode;
            dummyTail.prev = newNode;
            ++size;
            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }
            dummyHead.next.next.prev = dummyHead;
            dummyHead.next = dummyHead.next.next;
            --size;
            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }
            dummyTail.prev.prev.next = dummyTail;
            dummyTail.prev = dummyTail.prev.prev;
            --size;
            return true;
        }

        public int getFront() {
            return isEmpty() ? -1 : dummyHead.next.val;
        }

        public int getRear() {
            return isEmpty() ? -1 : dummyTail.prev.val;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == capacity;
        }
    }

    static class Node {
        public int val;
        public Node prev;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        MyCircularDeque circularDeque = new MyCircularDeque(3); // 设置容量大小为3
        System.out.println(circularDeque.insertLast(1));                    // 返回 true
        System.out.println(circularDeque.insertLast(2));                    // 返回 true
        System.out.println(circularDeque.insertFront(3));                    // 返回 true
        System.out.println(circularDeque.insertFront(4));                    // 已经满了，返回 false
        System.out.println(circularDeque.getRear());                // 返回 2
        System.out.println(circularDeque.isFull());                        // 返回 true
        System.out.println(circularDeque.deleteLast());                    // 返回 true
        System.out.println(circularDeque.insertFront(4));                    // 返回 true
        System.out.println(circularDeque.getFront());                // 返回 4
    }
}


